package com.ztom.daily.n2022.m5;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 找出游戏的获胜者
 * <p>
 * https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/
 *
 * @author ZhangTao
 */
public class Day04FindTheWinner {

    public int findTheWinner1(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }
        while (queue.size() > 1) {
            for (int i = 1; i < k; i++) {
                queue.offer(queue.poll());
            }
            queue.poll();
        }
        return queue.poll();
    }

    public int findTheWinner2(int n, int k) {
        if (n == 1) {
            return 1;
        }
        return (k + findTheWinner2(n - 1, k) - 1) % n + 1;
    }

    public int findTheWinner(int n, int k) {
        int winner = 1;
        for (int i = 2; i <= n; i++) {
            winner = (k + winner - 1) % i + 1;
        }
        return winner;
    }
}
